#define EIGEN_USE_MKL_ALL
#include <Eigen/Dense>
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include "../data_collector/dataset.hpp"
#include <limits>

const double MAX_DOUBLE = (std::numeric_limits<double>::max)();
const double MIN_DOUBLE = (std::numeric_limits<double>::min)();
const int MAX_INT = (std::numeric_limits<int>::max)();
const int MIN_INT = (std::numeric_limits<int>::min)();

using namespace Eigen;
const double EPSINON = 0.00000001;
int comDouble(double l, double r)
{
	double tmp = l - r;
	if (abs(tmp) <= EPSINON)
		return 0;
	if (tmp < 0)
		return -1;
	return 1;
}

struct myCompDouble
{
	bool operator()(const double l, const double r)
	{
		double tmp = l - r;
		return tmp < 0 ? (abs(tmp)>EPSINON ? true : false) : false;
	}
};

struct myCompString
{
	bool operator()(const std::string &l, const std::string &r)
	{
		return (l.compare(r)) < 0;
	}
};

typedef struct DecTree
{
	int iFeature;
	std::string label;
	std::map<double, DecTree*, myCompDouble> subTree;
}DecTree;

//for iFeature's value, split the dataSet, keep the feature order in the old records
DataSet *splitDataSet(const DataSet &dataSet, int iFeature, double value)
{
	DataSet *subSet = new DataSet;
	for (auto p = dataSet.cbegin(); p != dataSet.cend(); ++p)
		if (!comDouble(p->data(iFeature), value))
		{
			LabeledData d = { VectorXd(p->data.size() - 1), p->classLabel };
			for (int i = 0, j = 0; i < p->data.size(); ++i)
				if (i != iFeature)
					d.data(j++) = p->data(i);
			subSet->push_back(d);
		}
	return subSet;
}

double calcShannonEnt(const DataSet& dataSet)
{
	size_t len = dataSet.size();
	std::map<std::string, int> labelCounts;
	for (auto p = dataSet.cbegin(); p != dataSet.cend(); ++p)
		labelCounts[p->classLabel]++; //if not exists, automatically added by stl map
	ArrayXd tmp(labelCounts.size()), prop;
	int i = 0;
	for (auto p = labelCounts.cbegin(); p != labelCounts.cend(); ++p)
		tmp(i++) = p->second;
	prop = tmp / tmp.sum();
	tmp = -1 * (prop.log() / log(2));
	return (prop*tmp).sum();
}

//for every feature in current dataset , going to find the best feature
//ID3 ShannonEnt based
int ID3(const DataSet &ds)
{
	double bestInfo = MAX_DOUBLE;
	int bestInfoFeature;
	//for each feature
	for (int i = 0; i < (ds.at(0).data).size(); i++)
	{
		//fValueSets different feature value
		std::set<double, myCompDouble> fValueSets;
		for (auto p = ds.cbegin(); p != ds.cend(); ++p)
		{
			fValueSets.insert(p->data(i));
		}
		double ent = 0;
		//for every different value
		for (auto p = fValueSets.cbegin(); p != fValueSets.cend(); ++p)
		{
			DataSet *subDS = splitDataSet(ds, i, *p);
			double prop = (double)subDS->size() / ds.size();
			ent += calcShannonEnt(*subDS)*prop;
			delete(subDS);
		}
		//information gain for the same parent

		if (ent < bestInfo)
		{
			bestInfo = ent;
			bestInfoFeature = i;
		}
	}
	return bestInfoFeature;
}
//C4.5 ShannonEnt based
int C4_5(const DataSet &ds)
{
	double bestInfo = MIN_DOUBLE;
	int bestInfoFeature;
	double origin = calcShannonEnt(ds);
	//for each feature
	for (int i = 0; i < (ds.at(0).data).size(); i++)
	{
		//fValueSets different feature value
		std::map<double,int, myCompDouble> fValueMap;
		for (auto p = ds.cbegin(); p != ds.cend(); ++p)
		{
			fValueMap[p->data(i)]++;
		}
		double ent = 0;
		ArrayXd h(fValueMap.size());
		int j = 0;
		//for every different value
		for (auto p = fValueMap.cbegin(); p != fValueMap.cend(); ++p)
		{
			h(j++) = p->second;
			DataSet *subDS = splitDataSet(ds, i, p->first);
			double prop = (double)subDS->size() / ds.size();
			ent +=origin- calcShannonEnt(*subDS)*prop;
			delete(subDS);
		}
		h = h / h.sum();
		h = -1 * h*(h.log() / log(2));
		ent = ent / h.sum();
		//information gain for the same parent

		if (ent > bestInfo)
		{
			bestInfo = ent;
			bestInfoFeature = i;
		}
	}
	return bestInfoFeature;
}

DecTree *createTree(const DataSet &ds, std::vector<int> &curlabels,int(*info)(const DataSet&))
{
	std::vector<int> labels(curlabels);
	std::map<std::string, int, myCompString> classSet;
	for (auto p = ds.cbegin(); p != ds.cend(); ++p)
		classSet[p->classLabel]++;
	if (classSet.size() == 1)
	{
		DecTree *t = new DecTree;
		for (int i = 0; i < labels.size(); ++i)
			if (labels[i])
			{
				t->iFeature = i;
				t->label = classSet.cbegin()->first;
				break;
			}
		return t;
	}
	if (ds.at(0).data.size() == 1)
	{
		DecTree *t = new DecTree;
		int max = MIN_INT;
		std::string label;
		for (auto p = classSet.cbegin(); p != classSet.cend(); ++p)
		{
			if (p->second > max)
			{
				max = p->second;
				label = p->first;
			}
		}
		for (int i = 0; i < labels.size(); ++i)
			if (labels[i])
			{
				t->iFeature = i;
				t->label = label;
				break;
			}
		return t;
	}
	int bestFeature = info(ds);//in current dataset
	int i, j;
	for (i = 0, j = bestFeature + 1; i < labels.size() && j>0; ++i)
		if (labels[i] != 0)
			j--;
	labels[--i] = 0;
	DecTree *tree = new DecTree;
	tree->iFeature = i;
	std::set<double, myCompDouble> diffFs;
	for (auto p = ds.cbegin(); p != ds.cend(); ++p)
	{
		diffFs.insert(p->data(bestFeature));
	}
	for (auto p = diffFs.cbegin(); p != diffFs.cend(); ++p)
		tree->subTree[*p] = (createTree((*splitDataSet(ds, bestFeature, *p)), labels,info));
	return tree;
}



std::string getLabel(DecTree& tree, const LabeledData &data)
{
	if (!tree.label.empty())
		return tree.label;
	double min = MAX_DOUBLE;
	DecTree *t = nullptr;
	for (auto p = tree.subTree.cbegin(); p != tree.subTree.cend(); ++p)
	{
		double tmp = abs(p->first - data.data(tree.iFeature));
		if (tmp < min)
		{
			t = p->second;
			min = tmp;
		}
	}
	return getLabel((*t), data);
}

double validate(DecTree& tree, const DataSet &testData)
{
	double result = 0;
	int sum = 0;
	for (auto p = testData.cbegin(); p != testData.cend(); ++p)
	{
		if (!(getLabel(tree, *p).compare(p->classLabel)))
			sum++;
	}
	return (double)sum / testData.size();
}

int main()
{
	DataCollector d;
	//d.readDataFromFile("D:\\Project\\Machine_Learning\\DataSet\\balance-scale.data");
	d.readDataFromFile("D:\\Project\\Machine_Learning\\DataSet\\iris.data");
	//d.readDataFromFile("D:\\Project\\Machine_Learning\\DataSet\\winequality-white.csv");
	DataCollector x(d);
	ArrayXd result(2);
	result.setZero();
	for (int i = 0; i < 10; i++)
	{
		x.shuffle();
		DataSet *train = x.subDataList(0, 50);
		DataSet *test = x.subDataList(50,100);
		int c = x.DataList()->at(0).data.size();
		std::vector<int> labels(c, 1);
		DecTree *tree = createTree(*train, labels,ID3);
		result(0)+=validate(*tree, *test);
		tree = createTree(*train, labels, C4_5);
		result(1) += validate(*tree, *test);
	}
	std::cout << result / 10.0 << std::endl;
	return 0;
}